package com.chapter5.string;

/**
 * 
 * @ClassName: TST
 * @Description: 三向单词查找树
 * @author minjun
 * @date 2015年3月22日 下午12:20:48
 * 
 */
public class TST<Value> implements StringST<Value> {

	// 不需要初始化根节点，因为那个单词先插入，那个单词的首字母就是根节点位置
	private Node root;

	private class Node {
		Value value;
		char c;
		Node left, mid, right;

		public Node(char c) {
			this.c = c;
		}
	}

	@Override
	public void put(String key, Value value) {
		root = put(key, value, root, 0);
	}

	private Node put(String key, Value value, Node node, int d) {
		char c = key.charAt(d);
		if (node == null) {
			// 创建节点，并给新节点设置字母属性
			node = new Node(c);
		}
		if (d == key.length() - 1) {
			node.value = value;
			return node;
		}
		if (c > node.c) {
			// 如果当前要插入的字母更大，就往右边放
			node.right = put(key, value, node.right, d);
		} else if (c == node.c) {
			// 如果相等，就直接向下寻找合适的位置插入(只有在合适的时候才+1)
			node.mid = put(key, value, node.mid, d + 1);
		} else {
			// 如果更小，那就往左边放
			node.left = put(key, value, node.left, d);
		}
		return node;
	}

	@Override
	public Value get(String key) {
		Node node = get(key, root, 0);
		if (node == null)
			return null;
		return node.value;
	}

	private Node get(String key, Node node, int d) {
		if (node == null)
			return null;
		if (d == key.length() - 1) {
			return node;
		}
		char c = key.charAt(d);
		if (c > node.c) {
			node = get(key, node.right, d);
		} else if (c < node.c) {
			node = get(key, node.left, d);
		} else {
			node = get(key, node.mid, d + 1);
		}
		return node;
	}

	@Override
	public void delete(String key) {

	}

	@Override
	public boolean contains(String key) {
		return false;
	}

	@Override
	public boolean isEmpty() {
		return false;
	}

	@Override
	public int size() {
		return 0;
	}

	@Override
	public Iterable<String> keys() {
		return null;
	}

	@Override
	public Iterable<String> keysWithPrefix(String s) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Iterable<String> keysThatMatch(String s) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public String longestPrefixOf(String s) {
		// TODO Auto-generated method stub
		return null;
	}
}
